1057A - Bmail Computer Network - CodeForces Solution

#include <iostream>
#include <algorithm>
using namespace std;

const int mn = 2e5 + 10;
int p[mn];
int sol[mn];

int main()
{
    // numero de enrutadores (o nodos)
    int n;
    scanf("%d", &n);

    // p_i es igual al indice del enrutador al que se conecto el i-esimo enrutador
    // despues de comprarlo
    // el primer enrutador va a tener p_i = 0
    p[0] = 0;
    for (int i = 1; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }

    int k = n - 1, cnt = 0;
    // recorremos el grafo desde el nodo n -1 hacia arriba, hasta llegar a la raiz
    while (p[k] != k)
    {
        sol[cnt++] = k;
        // ponemos k igual a p_k
        k = p[k];
    }
    sol[cnt++] = 0;

    // ahora, imprimimos el arreglo sol en orden reverso
    reverse(sol, sol + cnt);
    for (int i = 0; i < cnt; i++)
    {
        printf("%d ", sol[i] + 1);
    }
    printf("\n");

    return 0;
}